/*
题目：拼车
车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）

给定整数 capacity 和一个数组 trips ,  trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。

当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。
https://leetcode.cn/problems/car-pooling
 */
class CarPooling {
    public boolean carPooling(int[][] trips, int capacity) {
        Arrays.sort(trips, new UpComparator()); //根据上车地点排序

        //根据下车地点构造小根堆
        PriorityQueue<int[]> heap = new PriorityQueue<> (new ArrComparator());

        for (int i = 0; i < trips.length && capacity >= 0; i++) {
            while (!heap.isEmpty() && trips[i][1] >= heap.peek()[2]) {  //如果当前上车地方大于公车上最小的下车地点
                capacity += heap.poll()[0]; //下车后空位空出来了
            }
            heap.offer(trips[i]);
            capacity -= trips[i][0];
        }

        return capacity >= 0;
    }
}

class UpComparator implements Comparator<int[]> {
    @Override
    public int compare(int[] o1, int[] o2) {
        return o1[1] - o2[1];
    }
}

class ArrComparator implements Comparator<int[]> {
    @Override
    public int compare(int[] o1, int[] o2) {
        return o1[2] - o2[2];
    }
}